package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/11 9:40
 * @description :https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
public class 最长递增子序列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLIS(new int[]{5,7,-24,12,13,2,3,12,5,6,35}));
    }
    /*
    //动态规划
    class Solution {
        public int lengthOfLIS(int[] nums) {
            int len = nums.length;
            int[] dp = new int[len];
            dp[0] = 1;
            int max = 1;
            for (int i = 1; i < len; i++) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                max = Math.max(max, dp[i]);
            }
            return max;
        }
    }
     */

//0 -24 2 3 5 6 35
    class Solution {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
            int[] d = new int[n + 1];
            int len = 1;
            d[len] = nums[0];
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > d[len]) {
                    d[++len] = nums[i];
                } else {
                    int l = 1;
                    int r = len;
                    int pos = 0;
                    while (l <= r) {
                        int mid = l + r >> 1;
                        if (d[mid] < nums[i]) {
                            pos = mid;
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    d[pos + 1] = nums[i];
                }
            }
            System.out.println(Arrays.toString(d));
            System.out.println(d[len]);
            return len;
        }
    }
}
